/*
8.25指定起点的邻接表有向带权最短路径.cpp
date:20201229 am 22:10
key:
1.输入时a-b，b-a都要
2.统一循环内尽量只用一个变量一次
*/
#include<iostream>
#include<string>
#include<stack>
const int MAX = 1E9;
using namespace std;
//用链表表示集合
class link_set
{
public:
	int value;
	link_set* next;
	link_set()
	{
		value = -1;
		next = NULL;
	}
	int size()
	{
		link_set* p1=this->next;
		int i = 1;
		if (this->value == -1)
		{
			return 0;
		}
		else
		{
			while (p1 != NULL)
			{
				
				p1 = p1->next;
				i += 1;
			}
			return i;
		}

	}
	int add(int num)
	{
		
		link_set* p1 = this;
		if (this->value == -1)
		{
			this->value=num;
		}
		else
		{
			while (p1->next != NULL)
			{
				if (p1->next->value == num)
				{
					return 0;
				}
				p1 = p1->next;
				
			}
			p1->next = new link_set;
			p1->next->value=num;
			
		}
	}
};
class node//边节点
{
public:
	int to_point;//vertex
	int length;
	node* p;//link
	node()
	{
		to_point = 0;
		length = 0;
		p = NULL;
	}
};
class main_point
{
public:
	int start_point;
	node* p;
	main_point()
	{
		start_point = 0;
		p = NULL;
	}
	//新边插入函数
	void add(int end_point, int length)
	{
		node* p1=this->p;//因为第一个指针类型和后面的指针类型不同
		if (p1 != NULL)//分成有无领边的情况
		{
			while (p1->p != NULL)
			{
				p1 = p1->p;
			}
			p1->p = new node;
			p1->p->to_point = end_point;
			p1->p->length = length;
		}
		else
		{
			this->p = new node;
			this->p->to_point = end_point;
			this->p->length = length;
		}
		
	}
	//此领接节点的未访问最小花费
	int char_min_cost(bool* flag, int&k)
	{
		node* p1 = this->p;
		int now_cost = MAX;
		if (p1 != NULL)//分成有无领边的情况
		{
			while (p1!= NULL)
			{
				if (flag[p1->to_point] == false)
				{
					if (p1->length < now_cost)
					{
						now_cost = p1->length;
						k = p1->to_point;
					}
				}

				p1 = p1->p;
			}
			return now_cost;
		}
		else
		{
			return now_cost;//这个点是个孤独点
		
		}

	}
	//此领接节点到指定终点的花费
	int find_length(int end_point1)
	{
		node* p1 = this->p;
		int now_cost = MAX;
		while (p1 != NULL)//分成有无领边的情况
		{
			if (p1->to_point == end_point1)
			{
				return p1->length;
			}
			p1 = p1->p;
		}
	}
};
//输出邻接表
void print_chart(main_point* arr,int N)
{
	int i, j, k, l, t;
	node*p1;
	for (i = 0; i < N; i++)
	{
		
		p1 = arr[i].p;
		while (p1 != NULL)
		{
			cout << arr[i].start_point << " ";
			cout << p1->to_point <<" "<< p1->length << endl;
			p1 = p1->p;
		}
	}
}


int main()

{
/*
5 6
1 2 10
1 3 18
2 4 5
3 2 5
4 5 2
5 3 2
*/
	int N, M,i,j,k,l,t;
	cout << "输入顶点数和边数" << endl;
	cin >> N >> M;

	//N大小的领阶数组头
	main_point* arr = new main_point [N];
	for (i = 0; i < N; i++)
	{
		arr[i].start_point= i;
	}
	//输入每条路的花费
	cout << "输入顶点和输入每条路的花费" << endl;
	for (i = 0; i < M; i++)
	{
		cin >> j>>k>>l;
		//注意这里是有向图
		arr[j-1].add(k-1, l);
		//arr[k - 1].add(j - 1, l);改加上这一句就是无向图
	}
	//print_chart(arr, N);
	//以0节点为起点
	int start = 0;

	//以0节点为起点的最短路径数组
	int* road = new int[N];
	for (i = 0; i < N; i++)//
	{
		road[i] = -1;
	}
	////以0节点为起点的最短距离存储数组
	int* min_cost = new int[N];
	//直接检查start所在链表,把start直达的都填入距离数组。
	node*p1=arr[start].p;
	for (i = 0; i < N; i++)//i只代表循环次数
	{
		min_cost[i] = MAX;
	}
	while (p1 != NULL)
	{
		min_cost[p1->to_point] = p1->length;
		p1 = p1->p;
	}
	//标记数组
	bool* flag = new bool[N];
	for (i = 0; i < N; i++)//i只代表循环次数
	{
		flag[i] = false;
	}
	//标记数组
	link_set* flag1 = new link_set;
	for (i = 0; i < N; i++)//i只代表循环次数
	{
		flag[i] = false;
	}
	//图各节点是否联通的标记
	bool imposs=false;
	//从0节点开始的最短路径,只需要找n-1次
	for (i = 0; i < N; i++)//i只代表循环次数
	{
		cout <<"本轮顶点 "<< start<<endl;
		flag1->add(start);
		cout << "已找到最短路径顶点的集合大小 " << flag1->size() << endl;
		road[i]=start;
		int now_cost = MAX;
		flag[start] = true;
		//对每个start到其余点花费的遍历

		//得到最小花费
		now_cost = arr[start].char_min_cost(flag,k);
		

		//最小花费更新花费数组
		if (min_cost[k] > min_cost[start] + now_cost)
		{
			min_cost[k] = min_cost[start] + now_cost;
		}
		//在最小花费数组里找最小
		l = MAX;//这里一定要用新的变量
		for (j = 0; j < N; j++)
		{
			//这个点不能被访问过
			if (flag[j] == false)
			{
			if (min_cost[j] < l)
				{
					
					l = min_cost[j];
					start = j;
				}
			}

		}
		
	}
	//距离累计值,是否构不成联通图，检查标记数组。
	int res = 0;
	for (i = 0; i < N; i++)
	{

		if (flag[i] == false)
		{
			imposs = true;
			break;
		};
	}
	if (imposs)
	{
		cout << "Impossible";
	}
	else
	{
		for (i = 0; i < N - 1; i++)
		{

			res += arr[road[i]].find_length(road[i + 1]);
		}
		cout <<"最短路径总长 "<< res;
	}




}